home *** CD-ROM | disk | FTP | other *** search
/ Giga Games 1 / Giga Games.iso / net / go / comp / pattern.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1991-06-05  |  13.4 KB  |  404 lines
  1. // copying
  2.     // Copyright (C) 1991 David Stoutamire (daves@alpha.ces.cwru.edu)
  3.     //
  4.     // This program is free software; you can redistribute it and/or modify
  5.     // it under the terms of the GNU General Public License as published by
  6.     // the Free Software Foundation, version 2.
  7.     // 
  8.     // This program is distributed in the hope that it will be useful,
  9.     // but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.     // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11.     // GNU General Public License for more details.
  12.     // 
  13.     // You should have received a copy of the GNU General Public License
  14.     // along with this program (file "COPYING"); if not, write to the Free
  15.     // Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  16.  
  17. #include "iku.h"
  18.  
  19. // class PatRep
  20.     PatRep* PatRep::duplicate() {
  21.         fatal("got call to PatRep::duplicate().");
  22.         }
  23.     patenum PatRep::identification() {
  24.         fatal("got call to PatRep::identification.");
  25.         }        
  26.     void PatRep::extract(PatternusingOpponent& op, Board& b, Move m) {
  27.         fatal("got call to PatRep::extract.");
  28.         }
  29.     bool PatRep::operator== (PatRep& vs) {
  30.         fatal("got call to PatRep::operator== (PatRep& vs).");
  31.         }
  32.     unsigned int PatRep::hash() {
  33.         fatal("got call to PatRep::hash().");
  34.         }
  35.     String PatRep::str() {
  36.         fatal("got call to PatRep::str().");
  37.         }
  38.  
  39. // class Pattern
  40.     Pattern::Pattern(patenum patterntouse=patnxn, String s="") {
  41.         switch(patterntouse) {
  42.             case patnxn:
  43.                 rep=new Patnxn(s);
  44.                 break;
  45.             case patgroup:
  46.                 rep=new Patgroup(s);
  47.                 break;
  48.             case patdiamond:
  49.                 rep=new Patdiamond(s);
  50.                 break;
  51.             default:
  52.                 fatal("Error in Pattern::Pattern().");
  53.             }
  54.         }
  55.     Pattern::Pattern(Pattern& p) {
  56.         rep=p.rep->duplicate();
  57.         }
  58.     Pattern::~Pattern() {
  59.         delete rep;
  60.         }
  61.     void Pattern::extract(PatternusingOpponent& op, 
  62.               Board& b, Move m) {
  63.         return(rep->extract(op,b,m));
  64.         }
  65.     bool Pattern::operator== (Pattern& vs) {
  66.         return((*rep)==(*(vs.rep)));
  67.         }
  68.     void Pattern::operator= (Pattern& p) {
  69.         delete rep;
  70.         rep=p.rep->duplicate();
  71.         }
  72.     unsigned int Pattern::hash(int hashsize=0) {
  73.     // return between 0...hashsize-1
  74.         int h=rep->hash();
  75.         if (hashsize!=0)
  76.             return((h>?(-h))%hashsize);
  77.         else
  78.             return h;
  79.         }
  80.     String Pattern::str() {
  81.         return(rep->str());
  82.         }
  83.  
  84. // class Patnxn
  85.     // Patnxn is a simple square pattern centered around move in question.
  86.     PatRep* Patnxn::duplicate() {
  87.         Patnxn *p=new Patnxn;
  88.     
  89.         p->rep=rep;
  90.         return(p);
  91.         }
  92.     Patnxn::Patnxn(String s="") {
  93.         rep=s;
  94.         }
  95.     String Patnxn::str() {
  96.         return(rep);
  97.         }
  98.     patenum Patnxn::identification() {
  99.         return(patnxn);
  100.         }
  101.     void Patnxn::extract(PatternusingOpponent& op, 
  102.              Board& b, Move m) {
  103.         if (m.kind!=play)
  104.             fatal("Asked to extract a play or resignation: "+m.str());
  105.  
  106.         int i,j;
  107.         rep="";
  108.         for (int sym=0;sym<8;sym++) {
  109.             char buf[(op.nxnsize*2+1)*(op.nxnsize*2+1)];
  110.             int at=0;
  111.             for (i=(-op.nxnsize);i<=op.nxnsize;i++)
  112.                 for (j=(-op.nxnsize);j<=op.nxnsize;j++) {
  113.                     if (i==0&&j==0)
  114.                         continue;
  115.                     Pos p(m.where.row+syma(i,j,sym),m.where.col+symb(i,j,sym));
  116.                     if (!p.valid()) 
  117.                         buf[at++]='c';
  118.                     else switch(b.board[p.row][p.col]) {
  119.                         case black: 
  120.                             if (b.turntoplay==blackstone)
  121.                                 buf[at++]='u';
  122.                             else
  123.                                 buf[at++]='t';
  124.                             break;
  125.                         case white:
  126.                             if (b.turntoplay==whitestone)
  127.                                 buf[at++]='u';
  128.                             else
  129.                                 buf[at++]='t';
  130.                             break;
  131.                         case empty:
  132.                             buf[at++]='e';
  133.                             break;
  134.                         default:
  135.                             fatal("Odd switch in genericextract.");
  136.                          }
  137.                     } 
  138.             buf[at]='\0';
  139.             if (String(buf)>rep)
  140.                 rep=buf;
  141.             }
  142.         }
  143.     bool Patnxn::operator== (PatRep& vs) {
  144.         if (vs.identification()!=patnxn)
  145.             fatal("type mismatch in patnxn operator==.");
  146.         return(rep==((Patnxn*)(&vs))->rep);
  147.         }
  148.     unsigned int Patnxn::hash() {
  149.         return(hashpjw((char*) rep));
  150.         }
  151.  
  152. // class Patdiamond
  153.     // simple diamond pattern.
  154.     PatRep* Patdiamond::duplicate() {
  155.         Patdiamond *p=new Patdiamond;
  156.     
  157.         p->rep=rep;
  158.         return(p);
  159.         }
  160.     Patdiamond::Patdiamond(String s="") {
  161.         rep=s;
  162.         }
  163.     String Patdiamond::str() {
  164.         return(rep);
  165.         }
  166.     patenum Patdiamond::identification() {
  167.         return(patdiamond);
  168.         }
  169.     void Patdiamond::extract(PatternusingOpponent& op,
  170.                  Board& b, Move m) {
  171.         if (m.kind!=play)
  172.             fatal("Asked to extract non-play in Patdiamond: "+m.str());
  173.  
  174.         int i=0,j=0;  //  initialized just to shut up g++
  175.         rep="";
  176.         for (int sym=0;sym<8;sym++) {
  177.             int seen=0;
  178.             char buf[999];
  179.             int at=0;
  180.             int currad,side,k;
  181.             for (currad=1;currad<=op.mindiamondsize||
  182.                      (currad<=op.maxdiamondsize&&seen<op.diamondmustsee);currad++)
  183.                 for (side=0;side<4;side++) 
  184.                     for (k=0;k<currad;k++) {
  185.                         switch (side) {
  186.                             case 0: i=k; j=currad-k;   break;
  187.                             case 1: i=currad-k; j= -k; break;
  188.                             case 2: i= -k; j=k-currad; break;
  189.                             case 3: i=k-currad; j=k;   break;
  190.                             }
  191.                         Pos p(m.where.row+syma(i,j,sym),m.where.col+symb(i,j,sym));
  192.                         if (!p.valid()) {
  193.                             buf[at++]='c';
  194.                             }
  195.                         else switch(b.board[p.row][p.col]) {
  196.                             case black: 
  197.                                 if (b.turntoplay==blackstone)
  198.                                     buf[at++]='u';
  199.                                 else
  200.                                     buf[at++]='t';
  201.                                 if (op.libscutoff!=0)
  202.                                     buf[at++]='0'+(b.libsat(p)<?op.libscutoff);
  203.                                 seen++;
  204.                                 break;
  205.                             case white:
  206.                                 if (b.turntoplay==whitestone)
  207.                                     buf[at++]='u';
  208.                                 else
  209.                                     buf[at++]='t';
  210.                                 if (op.libscutoff!=0)
  211.                                     buf[at++]='0'+(b.libsat(p)<?op.libscutoff);
  212.                                 seen++;
  213.                                 break;
  214.                             case empty:
  215.                                 buf[at++]='e';
  216.                                 break;
  217.                             default:
  218.                                 fatal("Odd switch in genericextract.");
  219.                             }
  220.                         } 
  221.             buf[at]='\0';
  222.             if (String(buf)>rep)
  223.                 rep=buf;
  224.             }
  225.         }
  226.     bool Patdiamond::operator== (PatRep& vs) {
  227.         if (vs.identification()!=patdiamond)
  228.             fatal("type mismatch in patdiamond operator==.");
  229.         return(rep==((Patdiamond*)(&vs))->rep);
  230.         }
  231.     unsigned int Patdiamond::hash() {
  232.         return(hashpjw((char*) rep));
  233.         }
  234.  
  235. // class Patgroup
  236.     // graph-based pattern extraction.  Very ugly code, sorry.
  237.     // globals used by class Patgroup
  238.         boardenum tbp[19][19];
  239.         const int maxgroups=361;
  240.         int seencounter;
  241.         bool weareblack;
  242.         char adj[maxgroups][maxgroups];
  243.         int adjcount[maxgroups];
  244.         int grp[19][19], grpcount;
  245.         boardenum grpcolor[maxgroups];
  246.         int grpseen[maxgroups];
  247.         int grpqueue[maxgroups];
  248.         int newqueue[maxgroups];
  249.         int numingrpq, numinnewq;
  250.         Board *Patgroup_bd;
  251.     PatRep* Patgroup::duplicate() {
  252.         Patgroup *p=new Patgroup;
  253.     
  254.         p->rep=rep;
  255.         return(p);
  256.         }
  257.     Patgroup::Patgroup(String s="") {
  258.         rep=s;
  259.         }
  260.     String Patgroup::str() {
  261.         return(rep);
  262.         }
  263.     patenum Patgroup::identification() {
  264.         return(patgroup);
  265.         }
  266.     void Patgroup::extract(PatternusingOpponent& op,
  267.                Board& b, Move m) {
  268.         int i,j;
  269.     
  270.         if (m.kind!=play) 
  271.             fatal("in Patgroup:: asked to extract something non-play: "+m.str());
  272.  
  273.         bool changed=false;
  274.         doboard(i,j) {
  275.             if (changed)
  276.                 break;
  277.             if (b.board[i][j]!=tbp[i][j])
  278.                 changed=true;
  279.             }
  280.         if (changed) {
  281.             doboard(i,j)
  282.                 tbp[i][j]=b.board[i][j];
  283.             Patgroup_groupify();    
  284.             }
  285.         weareblack=(b.turntoplay==black);
  286.         for (i=0;i<grpcount;i++)
  287.             grpseen[i]= -1;
  288.         numinnewq=1;
  289.         newqueue[0]=grp[m.where.row][m.where.col];
  290.         grpseen[newqueue[0]]=0;
  291.         seencounter=1;
  292.         rep="";
  293.         for (i=op.groupradius;i>0;i--)
  294.             rep+=Patgroup_gex(i);
  295.         }
  296.     bool Patgroup::operator== (PatRep& vs) {
  297.         if (vs.identification()!=patgroup)
  298.             fatal("type mismatch in patgroup operator==.");
  299.         return(rep==((Patgroup*)(&vs))->rep);
  300.         }
  301.     unsigned int Patgroup::hash() {
  302.         return(hashpjw((char*) rep));
  303.         }
  304.     void Patgroup_flood(int r, int c, int val, boardenum color) {
  305.         if (r<0||c<0||r>18||c>18||grp[r][c]!= -1||tbp[r][c]!=color)
  306.             return;
  307.         grp[r][c]=val;
  308.         if (color!=empty) {
  309.             Patgroup_flood(r-1,c,val,color);
  310.             Patgroup_flood(r+1,c,val,color);
  311.             Patgroup_flood(r,c-1,val,color);
  312.             Patgroup_flood(r,c+1,val,color);
  313.             }
  314.         }
  315.     void Patgroup_groupify() {
  316.         int i,j;
  317.         doboard(i,j)
  318.             grp[i][j]= -1;
  319.         grpcount=0;
  320.         doboard(i,j)
  321.             if (grp[i][j]== -1) {
  322.                 grpcolor[grpcount]=tbp[i][j];
  323.                 Patgroup_flood(i,j,grpcount++,tbp[i][j]);
  324.                 }
  325.         for (i=0;i<grpcount;i++)
  326.             for (j=0;j<grpcount;j++)
  327.                 adj[i][j]=0;
  328.         doboard(i,j) {
  329.             int g=grp[i][j];
  330.             if (i>0) {
  331.                 adj[g][grp[i-1][j]]=1;
  332.                 adj[grp[i-1][j]][g]=1;
  333.                 }
  334.             if (j>0) {
  335.                 adj[g][grp[i][j-1]]=1;
  336.                 adj[grp[i][j-1]][g]=1;
  337.                 }
  338.             if (i<18) {
  339.                 adj[g][grp[i+1][j]]=1;
  340.                 adj[grp[i+1][j]][g]=1;
  341.                 }
  342.             if (j<18) {
  343.                 adj[g][grp[i][j+1]]=1;
  344.                 adj[grp[i][j+1]][g]=1;
  345.                 }
  346.             }
  347.         for (i=0;i<grpcount;i++) {
  348.             adj[i][i]=0;
  349.             adjcount[i]=0;
  350.             for (j=0;j<grpcount;j++)
  351.                 adjcount[i]+=adj[i][j];
  352.             }
  353.         }
  354.     String Patgroup_gex(int iter) {
  355.         int i,j;
  356.         String s;
  357.     
  358.         numingrpq=0;
  359.         for (i=0;i<numinnewq;i++) {
  360.             for (j=0;j<grpcount;j++)
  361.                 if (adj[newqueue[i]][j])
  362.                     if (grpseen[j]>=0) 
  363.                         s+=form("#%d",grpseen[j]);
  364.             for (j=0;j<grpcount;j++)
  365.                 if (adj[newqueue[i]][j])
  366.                     if (grpseen[j]== -1&&grpcolor[j]==empty) {
  367.                         if (iter==1)
  368.                             s+="e";
  369.                         else
  370.                             s+=form("e%d",adjcount[j]);
  371.                         grpqueue[numingrpq++]=j;
  372.                         grpseen[j]=seencounter++;
  373.                         }
  374.             for (j=0;j<grpcount;j++)
  375.                 if (adj[newqueue[i]][j])
  376.                     if (grpseen[j]== -1)
  377.                         if ((weareblack&&grpcolor[j]==black) 
  378.                             ||((!weareblack)&&grpcolor[j]==white)) {
  379.                             if (iter==1)
  380.                                 s+="u";
  381.                             else
  382.                                 s+=form("u%d",adjcount[j]);
  383.                             grpqueue[numingrpq++]=j;
  384.                             grpseen[j]=seencounter++;
  385.                             }
  386.             for (j=0;j<grpcount;j++)
  387.                 if (adj[newqueue[i]][j])
  388.                     if (grpseen[j]== -1)
  389.                         if ((weareblack&&grpcolor[j]==white) 
  390.                             ||((!weareblack)&&grpcolor[j]==black)) {
  391.                             if (iter==1)
  392.                                 s+="t";
  393.                             else
  394.                                 s+=form("t%d",adjcount[j]);
  395.                             grpqueue[numingrpq++]=j;
  396.                             grpseen[j]=seencounter++;
  397.                             }
  398.             }
  399.         numinnewq=numingrpq;
  400.         for (i=0;i<numinnewq;i++)
  401.             newqueue[i]=grpqueue[i];
  402.         return(s+".");
  403.         }
  404.